package com.mgq.algorithm.link;

import com.mgq.algorithm.twotree.TreeNode;

/**
 * @author MaGuangQi
 * 最大二叉树 654题
 * @date 2022-02-18 14:00
 **/
public class MaxTree_654 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums,0,nums.length-1);
    }
    public TreeNode build(int[] nums, int left,int right){
        if(left>right){
            return null;
        }
        //首先找出最大值
        int maxVal=Integer.MIN_VALUE;
        int index=-1;
        //注意边界条件, i可以取到最右边
        for(int i=left;i<=right;i++){
            if(nums[i]>maxVal){
                maxVal=nums[i];
                index=i;
            }
        }
        //开始构建二叉树
        TreeNode root=new TreeNode(maxVal);
        //构造左树
        root.left=build(nums,left,index-1);
        //构造右树
        root.right=build(nums,index+1,right);
        //返回root
        return root;
    }
}
